package org.example.likou150.section;

import java.util.ArrayList;
import java.util.List;

// https://leetcode.cn/problems/insert-interval/?envType=study-plan-v2&envId=top-interview-150
public class Insert {
    public static void main(String[] args) {
        int[][] intervals=new int[][]{{1,2},{3,5},{6,7},{8,10},{12,16}};
        int[] newInterval=new int[]{4,8};
        Insert insert=new Insert();
        int[][] insert1 = insert.insert(intervals, newInterval);
        for (int i = 0; i < insert1.length; i++) {
            System.out.println(insert1[i][0] + " " + insert1[i][1]);
        }
    }

        public int[][] insert(int[][] intervals, int[] newInterval) {
            List<int[]> list = new ArrayList<>();
            for (int i = 0; i < intervals.length; i++) {
                int[] interval = intervals[i];
                if(interval[1]<newInterval[0]){
                    list.add(interval);
                }else if(interval[0]>newInterval[1]){
                    list.add(newInterval);
                    for(int j=i; j < intervals.length; j++){
                        list.add(intervals[j]);
                    }
                    return list.toArray(new int[list.size()][]);
                }else{
                    newInterval[0]=Math.min(interval[0], newInterval[0]);
                    newInterval[1]=Math.max(interval[1], newInterval[1]);
                }
            }
            list.add(newInterval);
            return list.toArray(new int[list.size()][]);
        }


//    public int[][] insert(int[][] intervals, int[] newInterval) {
//        List<int[]> result=new ArrayList<>();
//        for (int i = 0; i < newInterval.length; i++) {
//            int current = newInterval[i];
//            int index=0;
//            int last=intervals[0][0];
//            while(index<newInterval.length && intervals[index][0]<current){
//                last=Math.max(current,intervals[index][1]);
//                index++;
//            }
//            if(index==0){
//                result.add(new int[]{intervals[index][0], last});
//            }else {
//                result.add(new int[]{intervals[index-1][0], last});
//            }
//        }
//        return result.toArray(new int[result.toArray().length][]);
//    }
}
